# 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：n = 3
# 输出：5
#  
# 
#  示例 2： 
# 
#  
# 输入：n = 1
# 输出：1
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= n <= 19 
#  
#  Related Topics 树 二叉搜索树 数学 动态规划 二叉树 
#  👍 1369 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def numTrees(self, n: int) -> int:
        g = [0] * (n + 1)
        g[0], g[1] = 1, 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                g[i] += g[j-1] * g[i-j]
        return g[n]


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 1....n 遍历数字i 将 1...i-1 作为左子树, i + 1....n 作为右子树, 递归求和
# G(n) 表示 n 个数组成搜索树的个数
# G(n) = f(i, n)的和, G(0) == 1 G(1) == 1
# f(i, n) = G(i-1) 与 G(n-i) 的 笛卡尔积(组合), 数量为乘积
# G[n] = G (i-1) 与 G(n-i) 笛卡尔积(组合), 数量为乘积
#     def numTrees(self, n: int) -> int:
#         # 0 到 n n +1个数
#         g = [0] * (n + 1)
#         g[0], g[1] = 1, 1
#
#         for i in range(2, n + 1):
#             # 遍历当前位置前的所有数
#             for j in range(1, i + 1):
#                 g[i] += g[j - 1] * g[i - j]
#
#         return g[n]

if __name__ == '__main__':
    s = Solution()
    r1 = s.numTrees(3)
    assert r1 == 5, r1
